package _11_整理题目._3_字符串_递归_dfs_bfs_双指针._子串子序列_最值;

import org.junit.Test;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/minimum-window-substring/
 * https://leetcode-cn.com/problems/minimum-window-substring/solution/leetcode-76-zui-xiao-fu-gai-zi-chuan-cja-lmqz/
 *
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
 * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 *
 * 示例 1：
 *      输入：s = "ADOBECODEBANC", t = "ABC"
 *      输出："BANC"
 *
 * 思路：滑动窗口
 *      这道题要求我们返回字符串 s 中包含字符串 t 的全部字符的最小窗口，我们利用滑动窗口的思想解决这个问题。
 *      因此我们需要两个哈希表，wMap 哈希表维护的是 s 字符串中滑动窗口中各个字符出现多少次，tMap 哈希表维护的是 t 字符串各个字符出现多少次。
 *      如果 wMap 哈希表中包含 tMap 哈希表中的所有字符，并且对应的个数都大于等于 tMap 哈希表中各个字符的个数，
 *      那么说明当前的窗口是可行的，可行中的长度最短的滑动窗口就是答案。
 *
 *      1、记录 t 字符串的字符个数
 *          遍历 t 字符串，用 tMap 哈希表记录 t 字符串各个字符出现的次数。
 *      2、定义双指针指向 s 的首个字符
 *          定义两个指针 start 和 end，start 指针用于收缩窗口，end 指针用于延伸窗口，则区间 [start, end] 表示当前滑动窗口。
 *
 *      3、将当前的 s[i] 加入滑动窗口，判断，然后 end++ 扩展窗口
 *          计算有效字符数：对于新加入的字符s[i]，如果 wMap[s[i]] <= tMap[s[i]]，说明当前新加入的字符s[i]是必需的，count++
 *                                            (count 记录的是s字符串在窗口中 [start, end] 区间中满足t字符串的元素的个数)
 *          是否需要收缩窗口：
 *          是否需要更新答案：根据是否 count==t.length() && end-start+1 < min，更新 min 和 ans
 *
 *
 */
public class _051_最小覆盖子串 {

    private Map<Character,Integer> wMap = new HashMap<>();
    private Map<Character,Integer> tMap = new HashMap<>();

    public String minWindow(String s, String t) {
        for(int i = 0;i < t.length();i ++){
            tMap.put(t.charAt(i),tMap.getOrDefault(t.charAt(i), 0) + 1);
        }

        int start = 0, end = 0, count = 0; // 满足的字符数量
        String ans = "";
        int min = Integer.MAX_VALUE;
        while (end < s.length()) {
            char ch = s.charAt(end);
            wMap.put(ch, wMap.getOrDefault(ch, 0) + 1);
            if(tMap.containsKey(ch) && wMap.get(ch) <= tMap.get(ch)) count++;

            while(start < end && (!tMap.containsKey(s.charAt(start)) || tMap.get(s.charAt(start)) < wMap.get(s.charAt(start)))) {
                wMap.put(s.charAt(start), wMap.get(s.charAt(start)) - 1);
                if (wMap.get(s.charAt(start))==0) wMap.remove(s.charAt(start));
                start++;
            }

            if(count == t.length() && end - start + 1 < min){
                min = end - start + 1;
                ans = s.substring(start, end + 1);
            }

            end++;
        }
        return ans;
    }

    @Test
    public void main() {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow(s, t)); // "BANC"
    }

}
